package com.kehao.leetcode.hard.backtracking;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.*;

public class FindWordsSolution {
    private int[][] visit;

    private static class Trie{
        public String word;
        public Map<Character,Trie> children = new HashMap<>();
        public boolean isEnd;

        void insert(String word){
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if(!node.children.containsKey(c)){
                    node.children.put(c,new Trie());
                }
                node = node.children.get(c);
            }
            node.isEnd = true;
            node.word = word;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        visit = new int[board.length][board[0].length];
        List<String> result = new ArrayList<>();
        Trie root = new Trie();
        for (String word:words) {
            root.insert(word);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board,i,j,root,result);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int i, int j, Trie root, List<String> result) {
        visit[i][j] = 1;
        int[][] offset = {{-1,0},{0,-1},{1,0},{0,1}};
        if(root==null) return;
        if(root.children.containsKey(board[i][j])){
            if(root.children.get(board[i][j]).isEnd==true){
                result.add(root.children.get(board[i][j]).word);
                root.children.get(board[i][j]).isEnd = false;
            }
            for (int[] ints : offset) {
                int newi = i+ints[0];
                int newj = j+ints[1];
                if(newi<0||newi>=board.length||newj<0||newj>=board[0].length||visit[newi][newj]==1) continue;
                dfs(board,newi,newj,root.children.get(board[i][j]), result);
            }
        }
        visit[i][j] = 0;
    }

    @Test
    public void test(){
        String s = LeetCodeUtil.bracketTransform("board = [[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]], words = [\"oath\",\"pea\",\"eat\",\"rain\"]\n");
        System.out.println(s);
    }

    @Test
    public void test01(){
        char[][]board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain"};
        System.out.println(findWords(board, words));
    }

    @Test
    public void test02(){
        char[][]board = {{'a','b'},{'c','d'}};
        String[] words = {"abcb"};
        System.out.println(findWords(board, words));
    }

    @Test
    public void test03(){
        char[][]board = {{'a','b'}};
        String[] words = {"ba"};
        System.out.println(findWords(board, words));
    }
}
